package SimplePractice;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Stack;

import org.junit.Test;

public class Demo496 {
//	496. 下一个更大元素 I
//	给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
//
//	请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
//
//	nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
	
	public int[] nextGreaterElement(int[] nums1, int[] nums2) {
		
		LinkedList<Integer> stack = new LinkedList<>();
		Map<Integer, Integer> map = new HashMap<>();
		for(int i=0; i<nums1.length; i++) {
			map.put(nums1[i], i);
		}
		
		int[] ans = new int[nums1.length];
		
		for(int i=nums2.length-1; i>=0; i--) {
			
			while(!stack.isEmpty() && nums2[i] >= stack.peek()) {
				stack.pop();
			}
			
			if(map.containsKey(nums2[i])) {
				int greater = stack.isEmpty() ? -1 : stack.peek();
				int index = map.get(nums2[i]);
				ans[index] = greater;
			}
			
			stack.push(nums2[i]);
		}
		
		return ans;
		
    }
	
	@Test
	public void test_496() {
		int[] nums1 = {4,1,2};
		int[] nums2 = {1,3,4,2};
		int[] ans = nextGreaterElement(nums1, nums2);
		
		for(int num : ans) {
			System.out.println(num);
		}
	}

}
